Language/OS - Multiplatform Resource Library/LANGUAGE OS.iso/t3_1/doc.lha/documentation/manual/list.mss

Text File | 1987-06-30 | 15KB | 457 lines

@part[LIST, root "TMAN.MSS"]    @Comment{-*-System:TMAN-*-}
@chap[Lists]


@dc{ Say what a list is and why, what an atom is, what a pair is, etc.}

@dc{ Talk about various uses of lists:
as sets, as tables, as code trees. }

@dc{ Talk about external syntax for lists.  Whitespace, dots, etc. }

This section describes routines available for creating, examining,
and otherwise manipulating list structure.


@section[Predicates]

@info[NOTES="Type predicate",EQUIV="NULL"]
@desc[@el[](NULL? @i[object]) @yl[] @i[boolean]]
Returns true if @i[object] is the empty list (null).  Since the empty
list is also used for the logical false value, and non-false objects are
considered to be true, it turns out that @tc[NULL?] is the same as
@tc[NOT].
@EndDesc[NULL?]

@AnEquivE[Tfn="PAIR?",Efn="CONSP"]
@info[NOTES="Type predicate",EQUIV="PAIRP"]
@desc[@el[](PAIR? @i[object]) @yl[] @i[boolean]]
Returns true if @i[object] is a pair.
  @begin[ProgramExample]
(PAIR? '(A B C))   @ev[]  @r[true]
(PAIR? '(A . 15))  @ev[]  @r[true]
(PAIR? '())        @ev[]  @r[false]
(PAIR? 'FOO)       @ev[]  @r[false]
  @end[ProgramExample]
@EndDesc[PAIR?]

@info[NOTES="Type predicate",EQUIV="ATOM"]
@desc[@el[](ATOM? @i[object]) @yl[] @i[boolean]]
Returns true if @i[object] is an atom.
An atom is any object that isn't a pair.
  @begin[ProgramExample]
(ATOM? @i[object])  @ce[]  (NOT (PAIR? @i[object]))
  @end[ProgramExample]
@EndDesc[ATOM?]

@info[NOTES="Type predicate",EQUIV="LISTP"]
@desc[(LIST? @i[object]) @yl[] @i[boolean]]
Returns true if @i[object] is either a pair or the empty list.
  @begin[ProgramExample]
(LIST? '(A B C))   @ev[]  @r[true]
(LIST? '(A . 15))  @ev[]  @r[true]
(LIST? '())        @ev[]  @r[true]
(LIST? 'FOO)       @ev[]  @r[false]
  @end[ProgramExample]
@EndDesc[LIST?]

@Comment{ @info[NOTES="Type predicate"] it's not a type predicate. }
@desc[(PROPER-LIST? @i[object]) @yl[] @i[boolean]]
Returns true if @i[list] is a properly formed list, i.e., if its last
pair's cdr is null.
@begin[ProgramExample]
(PROPER-LIST? '(A B C))    @ev[]  @r[true]
(PROPER-LIST? '(A B . C))  @ev[]  @r[false]
(PROPER-LIST? '())         @ev[]  @r[true]
@end[ProgramExample]
@EndDesc[PROPER-LIST?]

@desc[(NULL-LIST? @i[list]) @yl[] @i[boolean]]
Like @tc[NULL?], but has an undefined effect (and may, for example,
signal an error) if its argument is not either a pair or null.
@wt[(NULL-LIST? @i[x])] is roughly the same as
@wt[(NULL? (PROCLAIM LIST? @i[x]))].
@EndDesc[NULL-LIST?]


@section[Constructors]

@desc[@el[](CONS @i[object1 object2]) @yl[] @i[pair]]
Returns a new pair whose car is @i[object1] and whose cdr is @i[object2].
  @begin[ProgramExample]
(CONS 'A '())            @ev[]  (A)
(CONS 'A 'B)             @ev[]  (A . B)
(CONS 'A '(B))           @ev[]  (A B)
(CONS 'A (CONS 'B '()))  @ev[]  (A B)
(CONS 'A (LIST 'B 'C))   @ev[]  (A B C)
  @end[ProgramExample]
@EndDesc[CONS]

@desc[@el[](LIST . @i[objects]) @yl[] @i[list]]
Returns a new list of its arguments.
  @begin[ProgramExample]
(LIST)                  @ev[]  ()
(LIST 'A)               @ev[]  (A)
(LIST 'A 'B)            @ev[]  (A B)
(LIST 'A (LIST 'B 'C))  @ev[]  (A (B C))
LIST  @ce[]  (LAMBDA THINGS THINGS)
  @end[ProgramExample]
@EndDesc[LIST]

@info[EQUIV="LIST*"]
@desc[(CONS* . @i[objects]) @yl[] @i[pair]]
@tc[CONS*] is a generalized @tc[CONS].
It returns a new, possibly improper, list,
by consing the initial @i[objects] onto the last @i[object].
  @begin[ProgramExample]
@tabclear
(CONS* 1 2 3)         @^@ev[]  (1 2 . 3)
(CONS* 'A 'B '(C D))  @ev[]  (A B C D)
(CONS* @i[object])  @\@ce[]  @i[object]
(CONS* @i[object1 object2])@\@ce[]  (CONS @i[object1 object2])
@tabclear
  @end[ProgramExample]
@EndDesc[CONS*]

@desc[(COPY-LIST @i[list]) @yl[] @i[list]]
Makes a @qu"top-level" copy of a list; that is, returns a new
list whose elements are the same as the original.
  @begin[ProgramExample]
(COPY-LIST @i[list])  @ce[]
  (COND ((NULL-LIST? @i[list]) '())
        (ELSE (CONS (CAR @i[list]) (COPY-LIST (CDR @i[list])))))

(COPY-LIST @i[list])  @ce[]  (MAP IDENTITY @i[list])
  @end[ProgramExample]
@EndDesc[COPY-LIST]


@section[List access]

@info[NOTES="Settable"]
@desc[@el[](CAR @i[pair]) @yl[] @i[object]]
Returns the car of the @i[pair].  By special dispensation,
@wt[(CAR '()) @ev[] ()], even though the empty list is not a pair.
@EndDesc[CAR]

@info[NOTES="Settable"]
@desc[@el[](CDR @i[pair]) @yl[] @i[object]]
Returns the cdr of the @i[pair].  By special dispensation,
@wt[(CDR '()) @ev[] ()], even though the empty list is not a pair.
@EndDesc[CDR]

@info[NOTES="Settable"]
@desc[(C...R @i[pair]) @yl[] @i[object]]
Compositions of @tc[CAR] and @tc[CDR], up to four deep, are defined.
@begin[ProgramExample]
(CADAR @i[x])   @ce[]  (CAR (CDR (CAR @i[x])))
(CADDDR @i[x])  @ce[]  (CAR (CDR (CDR (CDR @i[x]))))
@end[ProgramExample]
@EndDesc[C...R]

@info[NOTES="Settable"]
@desc[@el[](NTH @i[list n]) @yl[] @i[object]]
Returns the @i[n]@+[th] element of @i[list].  The first element (the car) is
@wt[(NTH @i[list] 0)], the second element is @wt[(NTH @i[list] 1)],
and so on.  In general, @i[list] must have at least @i[n]+1 elements.
  @dc{ not the nth! ... }
@begin[ProgramExample]
@tabclear
(NTH '(A B) 0)  @ev[]  A
(NTH '(A B) 1)  @ev[]  B
(NTH '(A B) 2)  @^@r[has an undefined effect]
(NTH '() @i[n])@\@r[has an undefined effect for any @i[n]]
@tabclear
@end[ProgramExample]
@EndDesc[NTH]

@info[NOTES="Settable"]
@desc[(NTHCDR @i[list n]) @yl[] @i[list]]
Returns the @i[n]@+[th] tail of @i[list].  In general, @i[list]
must have at least @i[n] tails.
@begin[ProgramExample]
@tabclear
(NTHCDR '(A B) 0)  @ev[]  (A B)
(NTHCDR '(A B) 1)  @ev[]  (B)
(NTHCDR '(A B) 2)  @ev[]  ()
(NTHCDR '(A B) 3)  @^@r[has an undefined effect]
(NTHCDR '() @i[n])@\@r[has an undefined effect for any nonzero @i[n]]
@tabclear
@end[ProgramExample]
    @BeginInset[Bug:]
    @tc[NTHCDR] doesn't handle @tc[SETTER] (i.e. is not settable) in
    @Timp[] 2.7.
    @EndInset[]
@EndDesc[NTHCDR]

@info[NOTES="Settable"]
@desc[@el[](LAST @i[list]) @yl[] @i[object]]
Returns the last element of @i[list].
@begin[ProgramExample]
(LAST '(A B C))  @ev[]  C
(LAST @i[list])  @ce[]  (CAR (LASTCDR @i[list]))
@end[ProgramExample]
@EndDesc[LAST]

@info[NOTES="Settable"]
@desc[(LASTCDR @i[list]) @yl[] @i[pair]]
Returns the last pair in @i[list].
@begin[ProgramExample]
(LASTCDR '(A B C))    @ev[]  (C)
(LASTCDR '(A B . C))  @ev[]  (B . C)
@end[ProgramExample]
    @BeginInset[Bug:]
    @tc[LASTCDR] doesn't handle @tc[SETTER] (i.e. is not settable) in
    @Timp[] 2.7.
    @EndInset[]
@EndDesc[LASTCDR]


@section[Lists as sequences]

@desc[@el[](LENGTH @i[list]) @yl[] @i[integer]]
Return the length of @i[list].
@begin[ProgramExample]
(LENGTH '())       @ev[]  0
(LENGTH '(A B C))  @ev[]  3
@end[ProgramExample]
@EndDesc[LENGTH]

@desc[@el[](APPEND . @i[lists]) @yl[] @i[list]]
Constructs a list which is the concatenation of @i[lists].
A new list is constructed, except that the result has
the last non-null argument as a tail.
@begin[ProgramExample]
(APPEND '(A B C) '(D E) '(F G))  @ev[]  (A B C D E F G)
@end[ProgramExample]
@EndDesc[APPEND]

@info[EQUIV="NCONC"]
@desc[(APPEND! . @i[lists]) @yl[] @i[list]]
Destructive version of @tc[APPEND].  Splices the lists together,
setting the cdr of the last pair in the first list to
the second list, and so on.  Returns its first non-null argument.
  @begin[ProgramExample]
(DEFINE L1 (LIST 'A 'B 'C))
(DEFINE L2 (LIST 'D 'E))
L1                @ev[]  (A B C)
(APPEND! L1 L2)   @ev[]  (A B C D E)
L1                @ev[]  (A B C D E)
(APPEND! '() L2)  @ev[]  (D E)
  @end[ProgramExample]
@EndDesc[APPEND!]

@desc[@el[](REVERSE @i[list]) @yl[] @i[list]]
Returns a new list whose elements are those of @i[list], in reverse order.
  @begin[ProgramExample]
(REVERSE '(A B C))  @ev[]  (C B A)
  @end[ProgramExample]
@EndDesc[REVERSE]

@info[EQUIV="NREVERSE, DREVERSE"]
@desc[(REVERSE! @i[list]) @yl[] @i[list]]
This is a @qu"destructive" version of @tc[REVERSE];
it allocates no storage for the result, but rather recycles
the pairs in the source @i[list]'s to form the result list.
@index[destructive]
@EndDesc[REVERSE!]

@desc[(SUBLIST @i[list] @i[start] @i[count]) @yl[] @i[list]]
Returns a list of @i[count] elements of @i[list],
beginning with element @i[start].
  @begin[ProgramExample]
(SUBLIST '(A B C D E F) 2 3)  @ev[]  (C D E)
  @end[ProgramExample]
@enddesc[SUBLIST]



@section[Lists as sets]

@desc[(MEMQ? @i[object list]) @yl[] @i[boolean]]
Returns true if @i[object] is an element of @i[list].
@begin[ProgramExample]
(MEMQ? 'B '(A B C))           @ev[]  @r[true]
(MEMQ? 'B '(A (B C) D))       @ev[]  @r[false]
(MEMQ? 'B '(B))               @ev[]  @r[true]
(MEMQ? 'B '())                @ev[]  @r[false]
(MEMQ? 17 '(10 17))           @ev[]  @r[undefined]
(MEMQ? "foo" '("foo" "bar"))  @ev[]  @r[undefined]
(LET ((X "foo"))
  (MEMQ? X (LIST 'B X)))      @ev[]  @r[true]
@end[ProgramExample]
@EndDesc[MEMQ?]

@desc[@el[](MEM? @i[predicate object list]) @yl[] @i[boolean]]
Returns true if @i[list] contains an object which
is equal to @i[object] according to @i[predicate],
which should be an equality predicate.
@begin[ProgramExample]
(MEM? = 17 '(10 17))                       @ev[]  @r[true]
(MEM? STRING-EQUAL? "foo" '("foo" "bar"))  @ev[]  @r[true]
@end[ProgramExample]
@EndDesc[MEM?]

@desc[(ANY? @i[predicate] . @i[lists]) @yl[] @i[boolean]]
Returns true if any element of @i[list] answers true to @i[predicate].
@begin[ProgramExample]
(ANY? NUMBER? '(FOO 15 BAR))  @ev[]  @r[true]
@end[ProgramExample]
@EndDesc[ANY?]

@desc[(EVERY? @i[predicate] . @i[lists]) @yl[] @i[boolean]]
Returns true if every element of @i[list] answers true to @i[predicate].
@begin[ProgramExample]
(EVERY? SYMBOL? '(A B C))  @ev[]  @r[true]
@end[ProgramExample]
@EndDesc[EVERY?]

@desc[(DELQ @i[object list]) @yl[] @i[list]]
Returns a list which is the same as the argument @i[list]
with all occurrences of @i[object] removed.
@EndDesc[DELQ]

@desc[@el[](DEL @i[predicate object list]) @yl[] @i[list]]
Returns a list which is the same as @i[list] except that all
elements which, according to @i[predicate],
are equal to @i[object], have been removed.
@i[Predicate] should be an equality predicate.
@ProgramExample[(DELQ @i[object list])  @ce[]  (DEL EQ? @i[object list])]
@EndDesc[DEL]

@info[EQUIV="DELQ"]
@desc[(DELQ! @i[object list]) @yl[] @i[list]]
Destructive version of @tc[DELQ].
Removes all occurrences of @i[object] from @i[list],
possibly altering it, and returns the new and/or modified list.
@EndDesc[DELQ!]

@desc[(DEL! @i[predicate object list]) @yl[] @i[list]]
Destructive version of @tc[DEL].
@ProgramExample[(DELQ! @i[object list])  @ce[]  (DEL! EQ? @i[object list])]
@EndDesc[DEL!]


@section[Mapping Procedures]

@info[EQUIV="MAPCAR"]
@desc[@el[](MAP @i[proc] . @i[lists]) @yl[] @i[list]]
Returns a list of the results of applying @i[proc] to successive elements
of the @i[lists]; the @i[n]@+[th] element of the result list is the result
of calling @i[proc] on the @i[n]@+[th] elements of the @i[lists].
The length of the result list is the same as the length of the shortest
of the @i[lists].
  @begin[ProgramExample]
(MAP (LAMBDA (X) (LIST 'A X)) '(CAT DOG))  @ev[]  ((A CAT) (A DOG))
(MAP + '(10 20) '(5 6))                    @ev[]  (15 26)
(MAP LIST '(A B) '(C D E) '(F))            @ev[]  ((A C F))
  @end[ProgramExample]
@EndDesc[MAP]

@info[EQUIV="MAPLIST"]
@desc[(MAPCDR @i[proc] . @i[lists]) @yl[] @i[list]]
@tc[MAPCDR] is similar to @tc[MAP], except that @i[proc] is applied to
successive @i[tails] of the @i[lists].
@EndDesc[MAPCDR]

@desc[(MAP! @i[proc] @i[list]) @yl[] @i[list]]
For each pair in @i[list], applies @i[proc] to the car of the pair,
and then modifies the pair so that its car is the value of the
application.
  @begin[ProgramExample]
(DEFINE L (LIST 'CAT 'DOG))  @ev[]  (CAT DOG)
(MAP! (LAMBDA (X) (LIST 'A X)) L)
L  @ev[]  ((A CAT) (A DOG))
  @end[ProgramExample]
@EndDesc[MAP!]

@info[EQUIV="MAPC"]
@desc[@el[](WALK @i[proc] . @i[lists]) @yl[] @i[undefined]]
This is similar to @tc[MAP] but the result is @comment{the value of the last
call to @i[proc] instead of a list of the result values.}
a value of no particular interest.
Thus @tc[WALK] is useful only for the side-effects that @i[proc] performs.
@comment{not for the return value.}
@EndDesc[WALK]

@info[EQUIV="MAP"]
@desc[(WALKCDR @i[proc] . @i[lists]) @yl[] @i[undefined]]
This is similar to @tc[MAPCDR] but the result is a value of no particular
interest.
@EndDesc[WALKCDR]


@section[Lists as associations]

@desc[(ASSQ @i[object list]) @yl[] @i[pair] @r[or] @i[false]]
  @begin[ProgramExample]
(ASSQ @i[object list])  @ce[]  (ASS EQ? @i[object list])
  @end[ProgramExample]
@EndDesc[ASSQ]

@desc[@el[](ASS @i[predicate object list]) @yl[] @i[pair] @r[or] @i[false]]
An @iix[association list]
is a list of pairs that represents
a @qu"lookup table" where the car of each pair matches a lookup key.  @tc[ASS]
and its related procedures search association lists by comparing
(applying @i[predicate]) the key (@i[object]) against the car of each
element of @i[list] (i.e., the caar of each tail).  If it finds a match,
it returns that element (the car of the tail).  If it finds no match,
it returns false.
  @begin[ProgramExample]
(ASS EQ? 'B '((A 10 20) (B 30 40) (C 50 60)))  @ev[]  (B 30 40)
(ASS = 9 '((1 Y) (4 Y) (9 Z) (12 P)))          @ev[]  (9 Z)
(ASS = 10 '((1 Y) (4 Y) (9 Z) (12 P)))         @ev[]  @r[false]
  @end[ProgramExample]
@EndDesc[ASS]


@section[Lists as stacks]

@tc[PUSH] and @tc[POP] permit a convenient syntax for the use of lists
in implementing simple stacks.  They are assignment forms, like @tc[SET]
and @tc[INCREMENT].  See section @ref[Assignmentsection] for a general
discussion of assignment forms.

@info[NOTES="Special form"]
@desc[(PUSH @i[location object]) @yl[] @i[undefined]]
@dc{ Bogus description - fix. }
Cons a pair whose car is @i[object] and whose cdr is
the value in @i[location] (usually a list), and
store the extended list back into @i[location].
  @begin[ProgramExample]
(LSET L '(34 55))  @ev[]  (34 55)
(PUSH L 21)
L                  @ev[]  (21 34 55)
(PUSH L '(A B C))
(PUSH (CAR L) 'D)
L                  @ev[]  ((D A B C) 21 34 55)
  @end[ProgramExample]

In general,
  @begin[ProgramExample]
(PUSH @i[location object])
  @ce[]  (SET @i[location] (CONS @i[object location]))
  @ce[]  (MODIFY @i[location] (LAMBDA (L) (CONS @i[object] L)))
  @end[ProgramExample]
@EndDesc[PUSH]

@info[NOTES="Special form"]
@desc[(POP @i[location]) @yl[] @i[object]]
The car of the value in @i[location]
(this value should be a pair) is returned.  As a side-effect,
the cdr of the list is stored back in the location.
  @begin[ProgramExample]
L        @ev[]  (21 34 55)
(POP L)  @ev[]  21
L        @ev[]  (34 55)
  @end[ProgramExample]
In general,
  @begin[ProgramExample]
(POP @i[location])  @ce[]  @~
  (BLOCK0 (CAR @i[location]) (SET @i[location] (CDR @i[location])))
                    @ce[]  @~
  (BLOCK0 (CAR @i[location]) (MODIFY @i[location] CDR))
  @end[ProgramExample]
@EndDesc[POP]